Reliable operation of software systems generally requires memory management that automatically ensures availability of dynamically allocated memory. Often known as garbage collection, this automatic task is performed by a garbage collector which recycles memory that will never be used again. Automatic garbage collection avoids the need for a programmer to explicitly deallocate memory blocks, and helps eliminate problems associated with memory leaks and premature memory frees. Objects are a collection of fields and methods. The fields can include slots which hold references to other objects, possible recursively. Since garbage collection can also simplify program development by reducing the need to manage storage used to instantiate objects, it is often available in modern languages, including Java and its variants, or C# (Microsoft Common Language Runtime (CLR)).
However, garbage collection does have a substantial associated runtime overhead, which overhead being in turn dependent on the specific garbage collection algorithm employed. Due to the well known Halting Problem, in general it is not possible for a garbage collector to determine exactly which memory objects are still alive and will be used by the program in the future. All garbage collectors use some approximation to determine aliveness of memory. In a “tracing” garbage collection, objects are determined to be alive if they are reachable. “Copying” garbage collection is a kind of tracing garbage collection that operates by relocating reachable objects (scavenging) and reclaiming objects left behind (such objects being unreachable and therefore dead).
For example, a two-space copy collector is a simple form of a copying garbage collector that divides available memory into two spaces. Memory objects can be in the first space, also known as the “from” or “old” space. Objects can be moved or allocated in the second space, also known as the “to” or “new” space. The first two spaces are collectively referred to as the area being collected or C space. Finally an object can be in a third uncollected space or U space. Objects are allocated in the first space until it is full. This space then becomes the “old” space. The reachable objects are then copied into the other “new” space (usually using a Cheney scan) and the previously allocated memory of the old space is reclaimed for the available memory pool. The Cheney scan is particularly efficient algorithm that requires no stack or other auxiliary space to maintain the list of memory objects not yet scanned. Allocation continues in the new space until it is filled, with the process then being repeated in reverse. As will be appreciated, improvements in copying efficiency of reachable objects translate into improvement in garbage collection and overall system performance.